      1  import java.util.Iterator;

      2  import java.util.List;

      3  import java.util.LinkedList;

      4  import java.util.Queue;

      5

      6  /**

      7     A tree in which each node has an arbitrary number of children.

      8  */

      9  public class Tree

     10  {

     11     private Node root;

     12

     13     class Node

     14     {

     15        public Object data;

     16        public List<Node> children;

     17

     18        /**

     19           Computes the size of the subtree whose root is this node.

     20           @return the number of nodes in the subtree

     21        */

     22        public int size()

     23        {

     24           int sum = 0;

     25           for (Node child : children) { sum = sum + child.size(); }

     26           return 1 + sum;

     27        }

     28     }

     29

     30     /**

     31        Constructs an empty tree.

     32     */

     33     public Tree()

     34     {

     35        root = null;

     36     }

     37

     38     /**

     39        Constructs a tree with one node and no children.

     40        @param rootData the data for the root

     41     */

     42     public Tree(Object rootData)

     43     {

     44        root = new Node();

     45        root.data = rootData;

     46        root.children = new LinkedList<Node>();

     47     }

     48

     49     /**

     50        Adds a subtree as the last child of the root.

     51     */

     52     public void addSubtree(Tree subtree)

     53     {

     54        root.children.add(subtree.root);

     55     }

     56

     57     /**

     58        Computes the size of this tree.

     59        @return the number of nodes in the tree

     60     */

     61     public int size()

     62     {

     63        if (root == null) { return 0; }

     64        else { return root.size(); }

     65     }

     66

     67     /**

     68        A visitor whose visit method is called for each visited node

     69        during a tree traversal.

     70     */

     71     public interface Visitor

     72     {

     73        /**

     74           This method is called for each visited node.

     75           @param data the data of the node

     76        */

     77        void visit(Object data);

     78     }

     79

     80     /**

     81        Traverses this tree in preorder.

     82        @param v the visitor to be invoked at each node

     83     */

     84     public void preorder(Visitor v) { preorder(root, v); }

     85

     86     /**

     87        Traverses the tree with a given root in preorder.

     88        @param n the root of the tree

     89        @param v the visitor to be invoked at each node

     90     */

     91     private static void preorder(Node n, Visitor v)

     92     {

     93        if (n == null) { return; }

     94        v.visit(n.data);

     95        for (Node c : n.children) { preorder(c, v); }

     96     }

     97

     98     /**

     99        Traverses this tree in postorder.

    100        @param v the visitor to be invoked at each node

    101     */

    102     public void postorder(Visitor v) { postorder(root, v); }

    103

    104     /**

    105        Traverses the tree with a given root in postorder.

    106        @param n the root of the tree

    107        @param v the visitor to be invoked at each node

    108     */

    109     private static void postorder(Node n, Visitor v)

    110     {

    111        if (n == null) { return; }

    112        v.visit(n.data);

    113        for (Node c : n.children) { postorder(c, v); }

    114     }

    115

    116     /**

    117        This iterator visits the nodes of a tree in

    118        breadth-first order.

    119     */

    120     class BreadthFirstIterator implements Iterator

    121     {

    122        private Queue<Node> q;

    123

    124        /**

    125           Constructs an iterator for a given tree.

    126           @param root the root of the tree

    127        */

    128        public BreadthFirstIterator(Node root)

    129        {

    130           q = new LinkedList<Node>();

    131           if (root != null) { q.add(root); }

    132        }

    133

    134        public boolean hasNext() { return q.size() > 0; }

    135

    136        public Object next()

    137        {

    138           Node n = q.remove();

    139           for (Node c : n.children) { q.add(c); }

    140           return n.data;

    141        }

    142

    143        public void remove() { throw new UnsupportedOperationException(); }

    144     }

    145

    146     public Iterator iterator()

    147     {

    148        return new BreadthFirstIterator(root);

    149     }

    150  }